#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"
#include "TypeDefin.h"

using namespace std;
/**
 *
 *给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
示例 2：
输入：head = [0,1,2], k = 4
输出：[2,0,1]
 *
 *
 * **/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode *reverseNode(ListNode *head) {
        if (!head || !head->next)
            return head;

        ListNode *res = reverseNode(head->next);
        head->next->next = head;
        head->next = nullptr;
        return res;
    }

    int getLen(ListNode *l) {
        auto head = l;
        int k = 0;
        while (head) {
            head = head->next;
            k++;
        }

        return k;

    }

    ListNode *rotateRight(ListNode *head, int k) {
        if (k == 0 || !head)
            return head;
        k = k % getLen(head);

        if (k == 0)
            return head;

        //反转全部
        ListNode *res = reverseNode(head);
        auto ht = res;
        head = res;
        //反转前K个
        int index = 1;
        while (index < k) {
            index++;
            ht = ht->next;
        }
        //此时ht为最后一个元素需要赋值为null 咱们保存下面的元素
        auto htNext = ht->next;
        ht->next = nullptr;
        auto ret = reverseNode(res);

        auto retNext = reverseNode(htNext);
        head->next = retNext;

        //
        //反转后面N-k个
        return ret;
    }
};